1. Field of the Invention
The present invention relates to a decoding method and decoding apparatus of a product code for improving the reliability of a digital communication system or digital recording system.
2. Description of Related Art
Although error-correcting codes such as Reed-Solomon codes have been utilized to improve reliability of digital communication/recording systems, more powerful error-correcting codes have been required recently to meet increasing speed and capacity of the systems. In general, high performance correcting codes require complicated decoding, which makes it difficult to be built into a device. However, using concatenated codes or product codes makes it possible to implement high-performance coding rather easily. In particular, the product codes have an advantage that they have large redundancy and error-correcting power because of the double encoding of information data. Accordingly, they are applied as an error-correcting method of CD-ROMs and DVDs. FIG. 1 is a diagram showing a construction of a product code. In FIG. 1, a code in the vertical direction is a binary linear code C1 with a code length N1 and information length K1, and a code in the horizontal direction is a binary linear code C2 with a code length N2 and information length K2. The block 1 designates information data, and blocks 2–4 each designate a check (redundant check).
Next, a coding method of the product code will be described with reference to FIG. 1. First, K1×K2 bit-information data are stored in the two-dimensional array (block 1) with K1 rows and K2 columns. The block 1 is represented by expression (1), where Di,j (i=1, 2, . . . , K1; j=1, 2, . . . , K2) is 0 or 1.
                              [                                                                      D                                      1                    ,                    1                                                                                                D                                      1                    ,                    2                                                                              ⋯                                                              D                                      1                    ,                    K2                                                                                                                        D                                      2                    ,                    1                                                                                                D                                      2                    ,                    2                                                                              ⋯                                                              D                                      2                    ,                    K2                                                                                                      ⋮                                            ⋮                                            ⋰                                            ⋮                                                                                      D                                      K1                    ,                    1                                                                                                D                                      K1                    ,                    2                                                                              ⋯                                                              D                                      K1                    ,                    K2                                                                                ]                ⁢                                  ⁢                  (                      Di            ,                          j              =              0                        ,            1                    )                                    (        1        )            
Next, individual columns from the first to K2 th column are provided with (N1–K1)-bit checks of the C1 code to construct a two-dimensional array with N1-rows and K2-columns (construction of the block 2).
Subsequently, individual rows from the first to N1th row are provided with (N2–K2)-bit checks of the C2 code to construct a two-dimensional array with N1-rows and N2-columns (construction of the blocks 3 and 4).
FIG. 2 is a block diagram showing a configuration of a digital communication system utilizing a product code, which is disclosed in Japanese patent application laid-open No. 7-202722. In FIG. 2, the reference numeral 201 designates an encoder for encoding input information data; 202 designates a modulator for converting a product code generated by the encoder 201 into a signal suitable for a communication channel; 203 designates the communication channel; 204 designates a demodulator for demodulating a received signal sent via the communication channel and for converting it to demodulated data; and 205 designates a decoder for decoding the demodulated data demodulated by the demodulator to estimate the information data. The encoder 201 and modulator 202 constitute a transmitter, and the demodulator 204 and the decoder 205 constitute a receiver.
Next, the operation of the system as shown in FIG. 2 will be described. The input K1×K2-bit information data are supplied to the encoder 201 for generating the product code with N1 rows and N2 columns. The product code generated is represented by a matrix C of following Expression 2. Although the elements of the product code C is represented by the binary 0 or 1, the binary 0 is represented as “+1”, and the binary 1 is represented by “−1” in the following.
                    C        =                              [                                                                                C                                          1                      ,                      1                                                                                                            C                                          1                      ,                      2                                                                                        ⋯                                                                      C                                          1                      ,                      N2                                                                                                                                        C                                          2                      ,                      1                                                                                                            C                                          2                      ,                      2                                                                                        ⋯                                                                      C                                          2                      ,                      N2                                                                                                                    ⋮                                                  ⋮                                                  ⋰                                                  ⋮                                                                                                  C                                          N1                      ,                      1                                                                                                            C                                          N1                      ,                      2                                                                                        ⋯                                                                      C                                          N1                      ,                      N2                                                                                            ]                    ⁢                                          ⁢                      (                                          C                                  i                  ,                  j                                            =                              ±                1                                      )                                              (        2        )            
The product code generated by the encoder 201 is supplied to the modulator 202 to be converted into the signal suitable for the communication channel 203, and is transmitted through the communication channel. It is assumed about the communication channel 203 that additive noise is superimposed on a transmission signal. The signal received through the communication channel 203 is supplied to the demodulator 204 of the receiver.
The demodulator 204 carries out shaping of the received signal to generate the demodulated data Y (expression (3)), the components of which are represented as Yi,j=Ci,j+Ni,j, where Ni,j are noise components. The demodulated data Y generated by the demodulator 204 is supplied to the decoder 205 for estimating the transmitted information data. In the following description, the demodulated data Y is denoted by {Y}, and is referred to as an input matrix.
                    Y        =                  [                                                                      Y                                      1                    ,                    1                                                                                                Y                                      1                    ,                    2                                                                              ⋯                                                              Y                                      1                    ,                    N2                                                                                                                        Y                                      2                    ,                    1                                                                                                Y                                      2                    ,                    2                                                                              ⋯                                                              Y                                      2                    ,                    N2                                                                                                      ⋮                                            ⋮                                            ⋰                                            ⋮                                                                                      Y                                      N1                    ,                    1                                                                                                Y                                      N1                    ,                    2                                                                              ⋯                                                              Y                                      N1                    ,                    N2                                                                                ]                                    (        3        )            
FIG. 3 is a flowchart illustrating the operation of the decoder 205. In FIG. 3, 301 is a step of inputting the input matrix {Y}; 302 is a step of setting initial values into a correction matrix {W} and a decision matrix {D}; 303A is a step of setting an initial value into a counter j; 304A is a step of calculating soft input vectors [Rk] (k=1, 2, . . . , N1); 305A is a step of calculating soft output vectors [Lk] (k=1, 2, . . . , N1); 306A is a step of updating the correction matrix {W}; 307A is a step of comparing the value of the counter j; and 308A is a step of incrementing the value of the counter j.
In addition, 303B is a step of setting an initial value into a counter i; 304B is a step of calculating soft input vectors [Rk] (k=1, 2, . . . , N2); 305B is a step of calculating soft output vectors [Lk] (k=1, 2, . . . , N2); 306B is a step of updating the correction matrix {W}; 307B is a step of comparing the value of the counter i; 308B is a step of incrementing the value of the counter i; 309 is a step of making a decision as to whether to iterate the decoding of the product code; and 310 is a step of outputting the decision matrix {D}.
Next, the operation will be described in more detail with reference to the flowchart of FIG. 3. First, at step 301, the N1×N2 input matrix {Y} given by the foregoing expression (3) is input. At the next step 302, the initial value zero is stored into all the elements of the N1×N2 correction matrix {W} given by the following expression (4).
                              W          =                      [                                                                                W                                          1                      ,                      1                                                                                                            W                                          1                      ,                      2                                                                                        ⋯                                                                      W                                          1                      ,                      N2                                                                                                                                        W                                          2                      ,                      1                                                                                                            W                                          2                      ,                      2                                                                                        ⋯                                                                      W                                          2                      ,                      N2                                                                                                                    ⋮                                                  ⋮                                                  ⋰                                                  ⋮                                                                                                  W                                          N1                      ,                      1                                                                                                            W                                          N1                      ,                      2                                                                                        ⋯                                                                      W                                          N1                      ,                      N2                                                                                            ]                          ⁢                                                      (        4        )            
Furthermore, initial values sgn{Y} are stored into all the elements of the N1×N2 decision matrix {D}. Specifically, the (i,j) elements Di,j of the decision matrix {D} is replaced by the code sgn(Yi,j) of the (i,j) elements Yi,j of the input matrix {Y}, where sgn is a function defined by the following expression (5).
                              sgn          ⁡                      (            x            )                          =                  {                                                                                          +                    1                                    ⁢                                                                          ⁢                                      (                                          x                      ≥                      0                                        )                                                                                                                                            -                    1                                    ⁢                                                                          ⁢                                      (                                          x                      <                      0                                        )                                                                                                          (        5        )            
At step 303A, the initial value one is set into the counter j. At the next step 304A, decoding of the C1 code is started. At step 304A, jth column of the input matrix {Y} and the jth column of the correction matrix {W} are added element by element. Specifically, according to expression (6), the (k,j) elements Yk,j of the input matrix {Y} are added to the (k,j) elements Wk,j of the correction matrix {W} to calculate the soft input values Rk (k=1, 2, . . . , N1).Rk←Yk,j+α·Wk,j (k=1, 2, . . . , N1)  (6)where α is an appropriate normalizing constant.
In the following description, the jth column of the input matrix is denoted by [Yk,j], that of the decision matrix is denoted by [Dk,j], and that of the correction matrix is denoted by [Wk,j], which are called input vector, decision vector and correction vector, respectively, according to the foregoing Japanese patent application laid-open No. 7-202722. At step 305A, the decision vector [Dk,j] is updated and the soft output vector [Lk] (k=1, 2, . . . , N1) is calculated. The details of step 305A will be described later. At step 306A, the differences obtained by subtracting the soft input vector from the soft output vector calculated at step 305A are stored in the jth column of the correction matrix {W} according to the following expression (7).Wk,j←Lk−Rk (k=1, 2, . . . , N1)  (7)
At step 307A, a decision is made as to whether the value of the counter j is less than N2. If it is less than N2, the value of the counter j is incremented at step 308A, followed by iterating the processing at step 304A and on. On the other hand, if the value of the counter j is N2, the processing proceeds to step 303B, at which the decoding of the C2 code is started. Up to this time, the update of all the elements of the correction matrix {W} has been completed.
At step 303B, the initial value one is set into the counter i. At the next step 304B, ith row of the input matrix {Y} and the ith row of the correction matrix {W} are added element by element. Specifically, according to the following expression (8), the (i,k) elements Yi,k of the input matrix are added to the (i,k) elements Wi,k of the correction matrix to calculate the soft input values Rk (k=1, 2, . . . , N2).Rk←Yi,k+α·Wi,k (k=1, 2, . . . , N2)  (8)where α is an appropriate normalizing constant.
In the following description, the ith row of the input matrix is denoted by [Yi,k], that of the decision matrix is denoted by [Di,k], and that of the correction matrix is denoted by [Wi,k], which are called input vector, decision vector and correction vector, respectively, as in the decoding of the foregoing C1 code. At step 305B, the decision vector [Di,k] is updated and the soft output vector [Lk] (k=1, 2, . . . , N2) is calculated. The details of step 305B will be described later. At step 306B, the differences obtained by subtracting the soft input vector from the soft output vector calculated at step 305B are stored in the ith rows of the correction matrix {W} according to the following expression (9).Wi,k←Lk−Rk (k=1, 2, . . . , N2)  (9)
At step 307B, a decision is made as to whether the value of the counter i is less than N1. If it is less than N1, the value of the counter i is incremented at step 308B, followed by iterating the processing at step 304B and on. On the other hand, if the value of the counter i is N1, the processing proceeds to step 309. Up to this time, the decoding of the C1 code and C2 code constituting the product codes has been completed once. At step 309, a decision is made as to whether the decoding of the C1 code is iterated or not. Usually, the decoding is completed when the iterated decoding has been carried out by a predetermined number of times. To iterate the decoding of the C1 code, the processing proceeds to step 303A to restart the decoding of the C1 code. On the other hand, to stop the decoding, the processing proceeds to step 310, at which the decision matrix {D} is output. Thus, the decoding processing is completed.
The data Di,j (i=1, 2, . . . , K1; j=1, 2, . . . , K2) stored in the K1×K2 decision matrix {D} output at step 310 represent the information data estimated by the decoding. Although the elements of the decision matrix {D} take a value “±1”, the value “+1” corresponds to a binary zero, and “−1” corresponds to a binary one.
Next, the soft input/soft output decoding of the C1 code at step 305A will be described. FIG. 4 is a flowchart illustrating the details of step 305A. Referring to FIG. 4, the operation will be described. At step 401, the soft input vector [Rk] and the decision vector [Dk] are input.
At step 402, p elements with least absolute values are selected from the soft input vector [R]. The positions of the p elements are denoted by k1, k2, . . . , and kp. At step 403, a test vector [Tk] is generated whose elements Tkm=0 or 1 at the p positions km (m=1, 2, . . . , p) selected at step 402, with the remaining elements Tk=0 (k≠km). Since the total of q=2p test vectors are present, they are denoted as [Ts] (s=1, 2, . . . , q) using the suffix s. The resultant test vectors [Ts] and the decision vector [Dk] are added element by element to generate words [Us] given by the following expression (10) for carrying out algebraic decoding of the C1 code. In expression (10), the elements “+1” and “−1” of the decision vector [Dk] is converted to a binary zero and one, respectively, and are subjected to modulo-2 addition.[Us]=[Dk]+[Ts] (s=1, 2, . . . , q)  (10)
At step 404, r candidate codewords [Ct]=(Ct1, Ct2, . . . , CtN1) (t=1, 2, . . . , r) are generated by decoding the q words [Us] (s=1, 2, . . . , q) generated at step 403 using the algebraic decoding of the C1 code.
At step 405, Euclidean distances Mt (t=1, 2, . . . , r) are calculated between the soft input vector [R] and the candidate codewords [Ct]. The Euclidean distance Mt between the soft input vector [R] and the candidate codewords [Ct] are given by the following expression (11).
                              M          t                =                              ∑                          k              =              1                        N1                    ⁢                                    (                                                R                  k                                -                                  C                  k                  t                                            )                        2                                              (        11        )            
At step 406, the codeword [Cd] that gives the minimum Euclidean distance (Mt≧Md) is selected. In addition, the codewords [Cd] are substituted into the decision vector according to the following expression (12).[D]←[Cd]  (12)
At step 407, the counter k is set at its initial value one, and the processing proceeds to step 408. At step 408, a decision is made as to whether any candidate codeword [Ct] (t=1, 2, . . . , r) is present, the kth value Ctk of which differs from the kth value Cdk of the codeword [Cd] selected at step 406, that is, whether the codeword [Ct] that satisfies Ctk=−Cdk is present or not. If it is not present, the processing proceeds to step 409. If it is present, the processing proceeds to step 410 at which a codeword that gives the least Euclidean distance among such codewords, which is called a concurrent codeword and denoted by [Cc], is selected, and the processing proceeds to step 411. At step 409, the soft output value given by the following expression (13) is calculated.Lk←βCdk  (13)where β is an appropriate value.
At step 411, the soft output value given by the following expression (14) is calculated.Lk←((Mc−Md)/4)Cdk  (14)where Mc is a Euclidean distance between the concurrent codeword [Cc] and the soft input vector [R].
At step 412, a decision is made as to whether the value of the counter k equals N1 or not. If they are not equal, the processing proceeds to step 413, at which the value of the counter k is incremented by one to iterate the processing from step 408 and on. On the other hand, if they are equal, the processing proceeds to step 414, at which the soft output vectors [Lk] and the decision vectors [Dk] are output, followed by completing the entire processing. Thus, the soft input/soft output decoding of the C1 code at step 305A has been completed. The soft input/soft output decoding of the C2 code at step 305B is the same as that of the C1 code.
As seen from the foregoing expressions (13) and (14), the conventional soft output value is calculated using at most two codewords among the candidate codewords generated at step 404.
With the foregoing configuration, the conventional decoding method of a product code has a problem of being unable to reflect the information provided by the candidate codewords other than the codeword [Cd] and the concurrent codeword [Cs] closest to the soft input vectors in terms of the Euclidean distance among the many codewords found at the codeword generating step.
In addition, it has a problem of losing information about the correction vector obtained at the previous decoding in the update of the correction matrix. This is because the new correction vector is obtained by subtracting the soft input vector from the soft output vector calculated by the soft input/soft output decoding.